package com.lin.algorithm.alo0518;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

/**
 * 取两个数组的并集
 */
public class UnionSet {

    public static void main(String[] args) {
//        int[] nums1 = {1, 0, 2, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 45, 3, 6, 1, 3, 2, 35, 3, 3, 2, 3, 5, 6, 7, 8, 9};
//        int[] nums2 = {0, 2, 35, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 6, 7, 8, 9};
//        8int[] nums1 = {1, 2, 2, 1};
//        int[] nums2 = {2, 2};
        int[] nums1 = {4, 9, 5};
        int[] nums2 = {49, 4, 9, 8, 4};
        System.out.println("union(nums1,nums2) = " + JSON.toJSONString(union(nums1, nums2)));
        System.out.println("unionUseArrayList(nums1,nums2) = " + JSON.toJSONString(unionUseArrayList(nums1, nums2)));
        System.out.println("union3(nums1,nums2) = " + JSON.toJSONString(union3(nums1, nums2)));
        System.out.println("union4(nums1,nums2) = " + JSON.toJSONString(union4(nums1, nums2)));
    }

    /**
     * 并集，集合只存唯一一个（使用 ArrayList 转换数组）
     */
    public static int[] unionUseArrayList(int nums1[], int nums2[]) {
        if (nums1 == null || nums2 == null || nums1.length <= 0 || nums2.length <= 0) {
            return new int[]{};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int left = 0, right = 0;
        Integer skip = null;
        ArrayList<Integer> list = new ArrayList<>();
        for (; left < nums1.length; left++) {
            for (; right < nums2.length; right++) {
                if ((skip != null && skip == nums1[left]) || nums1[left] < nums2[right]) {
                    break;
                } else if ((nums1[left] == nums2[right])) {
                    skip = nums1[left];
                    list.add(nums1[left]);
                    break;
                }
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }


    /**
     * 使用数组，不使用 ArrayList
     */
    public static int[] union(int nums1[], int nums2[]) {
        if (nums1 == null || nums2 == null || nums1.length <= 0 || nums2.length <= 0) {
            return new int[]{};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int left = 0, right = 0;
        Integer skip = null;
        int i = 0;
        int[] rs = new int[Math.min(nums1.length, nums2.length)];
        for (; left < nums1.length; left++) {
            for (; right < nums2.length; right++) {
                if ((skip != null && skip == nums1[left]) || nums1[left] < nums2[right]) {
                    break;
                } else if ((nums1[left] == nums2[right])) {
                    skip = nums1[left];
                    rs[i++] = nums1[left];
                    break;
                }
            }
        }
        return Arrays.copyOf(rs, i);
    }


    /**
     * 使用 Map
     */
    public static int[] union3(int nums1[], int nums2[]) {
        if (nums1 == null || nums2 == null || nums1.length <= 0 || nums2.length <= 0) {
            return new int[]{};
        }
        ArrayList<Integer> list = new ArrayList<>();
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            countMap.compute(nums1[i], (key, oldVal) -> {
                if (oldVal == null) {
                    return 1;
                } else {
                    return oldVal + 1;
                }
            });
        }
        for (int i = 0; i < nums2.length; i++) {
            int count;
            if ((count = countMap.getOrDefault(nums2[i], 0)) != 0) {
                countMap.put(nums2[i], count - 1);
                list.add(nums2[i]);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }


    /**
     * 使用 Map
     */
    public static int[] union4(int nums1[], int nums2[]) {
        if (nums1 == null || nums2 == null || nums1.length <= 0 || nums2.length <= 0) {
            return new int[]{};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int right = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int left = 0; left < nums1.length; left++) {
            for (; right < nums2.length; right++) {
                if (nums1[left] == nums2[right]) {
                    list.add(nums2[right++]);
                }
                if(left == nums1.length && left < nums2.length){
                    continue;
                }
                break;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

}

































